package com.uyong.study.algorithm.sort;

/**
 * 插入排序O(n^2),原地O(1),稳定
 * 
 * @author gonggy
 * @since 2019-01-29
 */
public class InsertSort implements ISort {

	@Override
	public void sort(int[] data) {
		if (data.length <= 1) {
			return;
		}
		for (int i = 1; i < data.length; i++) {
			int value = data[i];
			int j = i - 1;
			// 查找插入的位置
			for (; j >= 0; j--) {
				if (data[j] > value) {
					data[j + 1] = data[j]; // 移动数据
				} else {
					break;
				}
			}
			data[j + 1] = value; // 插入数据
		}
	}
}
